# -*- coding: utf-8 -*-
"""
@Time ： 2023/6/25 22:12
@Auth ： 叶东宇
@File ：implementStacksUsingQueue.py
"""


class MyQueue:

    def __init__(self):
        """
        in主要负责push，out主要负责pop
        """
        self.stack_in = []
        self.stack_out = []

    def push(self, x: int) -> None:
        """
        有新元素进来，就往in里面push
        """
        self.stack_in.append(x)

    def pop(self) -> int:
        """
        Removes the element from in front of queue and returns that element.
        """
        if self.empty():
            return None

        if self.stack_out:
            return self.stack_out.pop()
        else:
            for i in range(len(self.stack_in)):
                self.stack_out.append(self.stack_in.pop())
            return self.stack_out.pop()

    def peek(self) -> int:
        """
        Get the front element.
        """
        ans = self.pop()
        self.stack_out.append(ans)
        return ans

    def empty(self) -> bool:
        """
        只要in或者out有元素，说明队列不为空
        """
        return not (self.stack_in or self.stack_out)

class MyStacksUsingQueue:

    def __init__(self):
        """
        用的栈实现队列，那么用list时只能从尾部删除数据或者添加数据
        """
        self.stack_in = []
        self.stack_out = []

    def push(self, a: int) -> None:
        self.stack_in.append(a)

    """
    重点在于：
    1当我们要弹出队列最前面的数据时，存在这种情况：还没有数据被弹出过；有数据被弹出过
        因此，当还没有数据被弹出过时，即第一次弹出数据，需要把stack_in里面的数据全部转移到stack_out中，再从stack_out中的最后弹出数据
        当已经有数据弹出过时，那说明上一次弹出数据时，所有数据都转移到了stack_out，那么现在又可以分成两种情况：
            在上一次弹出数据后没有数据在添加了，所以这是只需要从stack_out中继续弹出数据即可。
            在上一次弹出数据后又继续添加了数据，这种情况下，在stack_out中的数据是比stack_in中现有的数据应该来的都早，所以应该更早被弹出去
            所以应该先把stack_out中的数据弹出去，即stack_out如果有数据的，那么当执行pop()函数时，应该首先弹出stack_out中的数据。
    
    2弹出数据要返回，不能只弹出不返回   
    """
    def pop(self):
        if self.empty():
            return None
        else:
            if len(self.stack_out) != 0:
                return self.stack_out.pop()
            else:
                for i in range(len(self.stack_in)):
                    self.stack_out.append(self.stack_in.pop())
                return self.stack_out.pop()

    def peek(self):
        a = self.pop()
        self.stack_out.append(a)
        return a


    def empty(self):
        return len(self.stack_in) == 0 and len(self.stack_out) == 0

if __name__ == "__main__":
    queue = MyQueue()
    queue.push(1)
    queue.push(2)
    print(queue.peek())
    print(queue.pop())
    print(queue.empty())